Strings

A comprehensive guide to string algorithms and techniques for Data Structures and Algorithms.

Basic String Operations
Pattern Matching Algorithms
String Manipulation Techniques
Palindrome Techniques
Anagram and Permutation
Sliding Window Techniques
Two Pointer Techniques
Advanced String Algorithms
Dynamic Programming with Strings
Usage Examples

Basic String Operations

1. String Traversal

function traverseString(str) {
    const result = [];

    // Method 1: Traditional for loop
    for (let i = 0; i < str.length; i++) {
        result.push(str[i]);
    }

    // Method 2: for...of loop
    for (const char of str) {
        result.push(char);
    }

    return result;
}

Time Complexity: O(n) | Space Complexity: O(1)

2. Character Frequency Count

function charFrequency(str) {
    const freq = {};

    for (const char of str) {
        freq[char] = (freq[char] || 0) + 1;
    }

    return freq;
}

// Using Map for better performance
function charFrequencyMap(str) {
    const freq = new Map();

    for (const char of str) {
        freq.set(char, (freq.get(char) || 0) + 1);
    }

    return freq;
}

3. String Comparison

function compareStrings(str1, str2) {
    if (str1.length !== str2.length) return false;

    for (let i = 0; i < str1.length; i++) {
        if (str1[i] !== str2[i]) return false;
    }

    return true;
}

// Case-insensitive comparison
function compareIgnoreCase(str1, str2) {
    return str1.toLowerCase() === str2.toLowerCase();
}

4. String Conversion Utilities

// Convert to different cases
function toCamelCase(str) {
    return str.toLowerCase().replace(/[^a-zA-Z0-9]+(.)/g, (m, chr) => chr.toUpperCase());
}

function toSnakeCase(str) {
    return str.replace(/\W+/g, " ")
              .split(/ |\B(?=[A-Z])/)
              .map(word => word.toLowerCase())
              .join('_');
}

function toKebabCase(str) {
    return str.replace(/\W+/g, " ")
              .split(/ |\B(?=[A-Z])/)
              .map(word => word.toLowerCase())
              .join('-');
}

Pattern Matching Algorithms

1. Naive Pattern Search

function naiveSearch(text, pattern) {
    const matches = [];
    const n = text.length;
    const m = pattern.length;

    for (let i = 0; i <= n - m; i++) {
        let j = 0;

        while (j < m && text[i + j] === pattern[j]) {
            j++;
        }

        if (j === m) {
            matches.push(i);
        }
    }

    return matches;
}

Time Complexity: O(nm) | Space Complexity: O(1)

2. KMP (Knuth-Morris-Pratt) Algorithm

function computeLPS(pattern) {
    const lps = new Array(pattern.length).fill(0);
    let len = 0;
    let i = 1;

    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}

function KMPSearch(text, pattern) {
    const matches = [];
    const n = text.length;
    const m = pattern.length;
    const lps = computeLPS(pattern);

    let i = 0; // text index
    let j = 0; // pattern index

    while (i < n) {
        if (pattern[j] === text[i]) {
            i++;
            j++;
        }

        if (j === m) {
            matches.push(i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] !== text[i]) {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    return matches;
}

Time Complexity: O(n + m) | Space Complexity: O(m)

3. Rabin-Karp Algorithm

function rabinKarp(text, pattern, prime = 101) {
    const matches = [];
    const n = text.length;
    const m = pattern.length;
    const base = 256;

    let patternHash = 0;
    let textHash = 0;
    let h = 1;

    // Calculate h = base^(m-1) % prime
    for (let i = 0; i < m - 1; i++) {
        h = (h * base) % prime;
    }

    // Calculate hash for pattern and first window of text
    for (let i = 0; i < m; i++) {
        patternHash = (base * patternHash + pattern.charCodeAt(i)) % prime;
        textHash = (base * textHash + text.charCodeAt(i)) % prime;
    }

    // Slide pattern over text
    for (let i = 0; i <= n - m; i++) {
        if (patternHash === textHash) {
            // Check characters one by one
            let match = true;
            for (let j = 0; j < m; j++) {
                if (text[i + j] !== pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) matches.push(i);
        }

        // Calculate hash for next window
        if (i < n - m) {
            textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
            if (textHash < 0) textHash += prime;
        }
    }

    return matches;
}

Time Complexity: O(nm) worst case, O(n + m) average | Space Complexity: O(1)

String Manipulation Techniques

1. String Reversal

// Method 1: Built-in methods
function reverseString1(str) {
    return str.split('').reverse().join('');
}

// Method 2: Two pointers
function reverseString2(str) {
    const chars = str.split('');
    let left = 0;
    let right = chars.length - 1;

    while (left < right) {
        [chars[left], chars[right]] = [chars[right], chars[left]];
        left++;
        right--;
    }

    return chars.join('');
}

// Method 3: Recursive
function reverseString3(str) {
    if (str.length <= 1) return str;
    return str[str.length - 1] + reverseString3(str.slice(0, -1));
}

2. Remove Characters

function removeChar(str, charToRemove) {
    return str.split('').filter(char => char !== charToRemove).join('');
}

function removeCharsRegex(str, pattern) {
    return str.replace(new RegExp(pattern, 'g'), '');
}

function removeVowels(str) {
    return str.replace(/[aeiouAEIOU]/g, '');
}

function removeConsonants(str) {
    return str.replace(/[^aeiouAEIOU\s]/g, '');
}

3. String Compression

function compress(str) {
    if (!str) return '';

    let compressed = '';
    let count = 1;

    for (let i = 1; i < str.length; i++) {
        if (str[i] === str[i - 1]) {
            count++;
        } else {
            compressed += str[i - 1] + (count > 1 ? count : '');
            count = 1;
        }
    }

    // Add the last character group
    compressed += str[str.length - 1] + (count > 1 ? count : '');

    return compressed.length < str.length ? compressed : str;
}

function decompress(str) {
    let result = '';
    let i = 0;

    while (i < str.length) {
        const char = str[i];
        let count = '';
        i++;

        // Read the number
        while (i < str.length && !isNaN(str[i])) {
            count += str[i];
            i++;
        }

        const repeatCount = count === '' ? 1 : parseInt(count);
        result += char.repeat(repeatCount);
    }

    return result;
}

Palindrome Techniques

1. Check if String is Palindrome

// Simple approach
function isPalindrome1(str) {
    const cleaned = str.toLowerCase().replace(/[^a-z0-9]/g, '');
    return cleaned === cleaned.split('').reverse().join('');
}

// Two pointers approach
function isPalindrome2(str) {
    const cleaned = str.toLowerCase().replace(/[^a-z0-9]/g, '');
    let left = 0;
    let right = cleaned.length - 1;

    while (left < right) {
        if (cleaned[left] !== cleaned[right]) {
            return false;
        }
        left++;
        right--;
    }

    return true;
}

// Recursive approach
function isPalindromeRecursive(str, start = 0, end = str.length - 1) {
    if (start >= end) return true;
    if (str[start] !== str[end]) return false;
    return isPalindromeRecursive(str, start + 1, end - 1);
}

2. Longest Palindromic Substring

// Expand around centers
function longestPalindrome(s) {
    if (!s || s.length < 2) return s || '';

    let start = 0;
    let maxLength = 1;

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            const currentLength = right - left + 1;
            if (currentLength > maxLength) {
                start = left;
                maxLength = currentLength;
            }
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);     // Odd length palindromes
        expandAroundCenter(i, i + 1); // Even length palindromes
    }

    return s.substring(start, start + maxLength);
}

3. All Palindromic Substrings

function countPalindromes(s) {
    let count = 0;

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);     // Odd length
        expandAroundCenter(i, i + 1); // Even length
    }

    return count;
}

function getAllPalindromes(s) {
    const palindromes = [];

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            palindromes.push(s.substring(left, right + 1));
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);
        expandAroundCenter(i, i + 1);
    }

    return [...new Set(palindromes)]; // Remove duplicates
}

Anagram and Permutation

1. Check if Two Strings are Anagrams

// Sorting approach
function isAnagram1(str1, str2) {
    if (str1.length !== str2.length) return false;

    const sorted1 = str1.toLowerCase().split('').sort().join('');
    const sorted2 = str2.toLowerCase().split('').sort().join('');

    return sorted1 === sorted2;
}

// Character frequency approach
function isAnagram2(str1, str2) {
    if (str1.length !== str2.length) return false;

    const freq = {};

    // Count characters in first string
    for (const char of str1.toLowerCase()) {
        freq[char] = (freq[char] || 0) + 1;
    }

    // Subtract characters from second string
    for (const char of str2.toLowerCase()) {
        if (!freq[char]) return false;
        freq[char]--;
    }

    return true;
}

2. Group Anagrams

function groupAnagrams(strs) {
    const groups = {};

    for (const str of strs) {
        const key = str.split('').sort().join('');
        if (!groups[key]) {
            groups[key] = [];
        }
        groups[key].push(str);
    }

    return Object.values(groups);
}

// Alternative approach using character frequency
function groupAnagramsFreq(strs) {
    const groups = {};

    for (const str of strs) {
        const freq = new Array(26).fill(0);
        for (const char of str) {
            freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = freq.join(',');

        if (!groups[key]) {
            groups[key] = [];
        }
        groups[key].push(str);
    }

    return Object.values(groups);
}

3. Generate All Permutations

function permutations(str) {
    if (str.length <= 1) return [str];

    const result = [];

    for (let i = 0; i < str.length; i++) {
        const char = str[i];
        const remaining = str.slice(0, i) + str.slice(i + 1);
        const perms = permutations(remaining);

        for (const perm of perms) {
            result.push(char + perm);
        }
    }

    return result;
}

// Iterative approach
function permutationsIterative(str) {
    let perms = [''];

    for (const char of str) {
        const newPerms = [];
        for (const perm of perms) {
            for (let i = 0; i <= perm.length; i++) {
                newPerms.push(perm.slice(0, i) + char + perm.slice(i));
            }
        }
        perms = newPerms;
    }

    return perms;
}

Sliding Window Techniques

1. Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
    const seen = new Set();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }

        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

2. Minimum Window Substring

function minWindow(s, t) {
    if (s.length < t.length) return '';

    const tFreq = {};
    for (const char of t) {
        tFreq[char] = (tFreq[char] || 0) + 1;
    }

    let left = 0;
    let minLen = Infinity;
    let minStart = 0;
    let matched = 0;
    const windowFreq = {};

    for (let right = 0; right < s.length; right++) {
        const rightChar = s[right];
        windowFreq[rightChar] = (windowFreq[rightChar] || 0) + 1;

        if (tFreq[rightChar] && windowFreq[rightChar] === tFreq[rightChar]) {
            matched++;
        }

        while (matched === Object.keys(tFreq).length) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }

            const leftChar = s[left];
            windowFreq[leftChar]--;
            if (tFreq[leftChar] && windowFreq[leftChar] < tFreq[leftChar]) {
                matched--;
            }
            left++;
        }
    }

    return minLen === Infinity ? '' : s.substring(minStart, minStart + minLen);
}

3. Longest Repeating Character Replacement

function characterReplacement(s, k) {
    const freq = {};
    let left = 0;
    let maxFreq = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        freq[s[right]] = (freq[s[right]] || 0) + 1;
        maxFreq = Math.max(maxFreq, freq[s[right]]);

        // If window size - max frequency > k, shrink window
        if (right - left + 1 - maxFreq > k) {
            freq[s[left]]--;
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Two Pointer Techniques

1. Valid Palindrome

function isPalindromeAlphanumeric(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !isAlphanumeric(s[left])) {
            left++;
        }
        while (left < right && !isAlphanumeric(s[right])) {
            right--;
        }

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

function isAlphanumeric(char) {
    const code = char.charCodeAt(0);
    return (code >= 48 && code <= 57) ||  // 0-9
           (code >= 65 && code <= 90) ||  // A-Z
           (code >= 97 && code <= 122);   // a-z
}

2. Two Sum in Sorted Array (String Version)

function twoSumStrings(strings, target) {
    let left = 0;
    let right = strings.length - 1;

    while (left < right) {
        const current = strings[left] + strings[right];

        if (current === target) {
            return [left, right];
        } else if (current < target) {
            left++;
        } else {
            right--;
        }
    }

    return [-1, -1];
}

3. Container With Most Water (String Analogy)

function longestCommonPrefix(strs) {
    if (!strs || strs.length === 0) return '';

    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === '') return '';
        }
    }

    return prefix;
}

Advanced String Algorithms

1. Z Algorithm

function zAlgorithm(s) {
    const n = s.length;
    const z = new Array(n).fill(0);
    let left = 0;
    let right = 0;

    for (let i = 1; i < n; i++) {
        if (i <= right) {
            z[i] = Math.min(right - i + 1, z[i - left]);
        }

        while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
            z[i]++;
        }

        if (i + z[i] - 1 > right) {
            left = i;
            right = i + z[i] - 1;
        }
    }

    return z;
}

function searchWithZ(text, pattern) {
    const combined = pattern + '$' + text;
    const z = zAlgorithm(combined);
    const matches = [];

    for (let i = 0; i < z.length; i++) {
        if (z[i] === pattern.length) {
            matches.push(i - pattern.length - 1);
        }
    }

    return matches;
}

2. Manacher's Algorithm (Longest Palindromic Substring)

function manacher(s) {
    // Transform string: "abc" -> "^#a#b#c#$"
    const processed = '^#' + s.split('').join('#') + '#$';
    const n = processed.length;
    const p = new Array(n).fill(0);
    let center = 0;
    let right = 0;

    for (let i = 1; i < n - 1; i++) {
        const mirror = 2 * center - i;

        if (i < right) {
            p[i] = Math.min(right - i, p[mirror]);
        }

        // Expand around center i
        while (processed[i + (1 + p[i])] === processed[i - (1 + p[i])]) {
            p[i]++;
        }

        // If palindrome centered at i extends past right, adjust center and right
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }

    return p;
}

function longestPalindromeManacher(s) {
    const p = manacher(s);
    let maxLen = 0;
    let centerIndex = 0;

    for (let i = 0; i < p.length; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            centerIndex = i;
        }
    }

    const start = Math.floor((centerIndex - maxLen) / 2);
    return s.substring(start, start + maxLen);
}

3. Suffix Array

function buildSuffixArray(s) {
    const n = s.length;
    const suffixes = [];

    for (let i = 0; i < n; i++) {
        suffixes.push({
            index: i,
            suffix: s.substring(i)
        });
    }

    suffixes.sort((a, b) => a.suffix.localeCompare(b.suffix));

    return suffixes.map(suffix => suffix.index);
}

function longestCommonSubstring(str1, str2) {
    const combined = str1 + '#' + str2;
    const suffixArray = buildSuffixArray(combined);
    const n = combined.length;

    let maxLength = 0;
    let result = '';

    for (let i = 0; i < n - 1; i++) {
        const idx1 = suffixArray[i];
        const idx2 = suffixArray[i + 1];

        // Check if suffixes are from different strings
        const fromDifferentStrings =
            (idx1 < str1.length && idx2 > str1.length) ||
            (idx1 > str1.length && idx2 < str1.length);

        if (fromDifferentStrings) {
            const suffix1 = combined.substring(idx1);
            const suffix2 = combined.substring(idx2);

            let commonLength = 0;
            const minLength = Math.min(suffix1.length, suffix2.length);

            while (commonLength < minLength &&
                   suffix1[commonLength] === suffix2[commonLength]) {
                commonLength++;
            }

            if (commonLength > maxLength) {
                maxLength = commonLength;
                result = suffix1.substring(0, commonLength);
            }
        }
    }

    return result;
}

Dynamic Programming with Strings

1. Longest Common Subsequence

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

function getLCSString(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    // Fill DP table
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Reconstruct LCS
    let lcs = '';
    let i = m, j = n;

    while (i > 0 && j > 0) {
        if (text1[i - 1] === text2[j - 1]) {
            lcs = text1[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    return lcs;
}

2. Edit Distance (Levenshtein Distance)

function editDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    // Initialize base cases
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],     // deletion
                    dp[i][j - 1],     // insertion
                    dp[i - 1][j - 1]  // substitution
                );
            }
        }
    }

    return dp[m][n];
}

3. Distinct Subsequences

function numDistinct(s, t) {
    const m = s.length;
    const n = t.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    // Empty subsequence can be formed in one way
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[m][n];
}

Usage Examples

console.log("=== String Algorithms Demo ===");

// Basic operations
const str = "Hello World";
console.log("Original:", str);
console.log("Reversed:", reverseString2(str));
console.log("Character frequency:", charFrequency(str.toLowerCase()));

// Pattern matching
const text = "ABABDABACDABABCABCABCABCABC";
const pattern = "ABABCABCAB";
console.log("Naive search:", naiveSearch(text, pattern));
console.log("KMP search:", KMPSearch(text, pattern));
console.log("Rabin-Karp search:", rabinKarp(text, pattern));

// String manipulation
const testStr = "aabcccccaaa";
console.log("Compressed:", compress(testStr));
console.log("Decompressed:", decompress(compress(testStr)));

// Palindrome checks
const palindromeTests = ["racecar", "A man a plan a canal Panama", "race a car"];
palindromeTests.forEach(test => {
    console.log(`"${test}" is palindrome:`, isPalindrome2(test));
});

console.log("Longest palindrome in 'babad':", longestPalindrome("babad"));
console.log("All palindromes in 'aab':", getAllPalindromes("aab"));

// Anagrams
console.log("'listen' and 'silent' are anagrams:", isAnagram2("listen", "silent"));
console.log("Group anagrams:", groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));

// Sliding window
console.log("Longest substring without repeating:", lengthOfLongestSubstring("abcabcbb"));
console.log("Min window substring:", minWindow("ADOBECODEBANC", "ABC"));

// Advanced algorithms
console.log("Z-algorithm for 'aabaaba':", zAlgorithm("aabaaba"));
console.log("LCS of 'ABCDGH' and 'AEDFHR':", getLCSString("ABCDGH", "AEDFHR"));
console.log("Edit distance between 'horse' and 'ros':", editDistance("horse", "ros"));

Time Complexity Summary

Algorithm	Time Complexity	Space Complexity	Use Case
Basic Operations
Traversal	`O(n)`	`O(1)`	Basic string processing
Character Frequency	`O(n)`	`O(k)` where k = unique chars	Anagram detection
String Comparison	`O(n)`	`O(1)`	Equality checking
Pattern Matching
Naive Search	`O(nm)`	`O(1)`	Simple pattern finding
KMP Algorithm	`O(n + m)`	`O(m)`	Efficient pattern matching
Rabin-Karp	`O(n + m)` avg, `O(nm)` worst	`O(1)`	Multiple pattern search
Z Algorithm	`O(n)`	`O(n)`	Pattern matching, periodicity
String Manipulation
Reverse String	`O(n)`	`O(1)` to `O(n)`	String reversal
Compression	`O(n)`	`O(1)`	Data compression
Remove Characters	`O(n)`	`O(1)` to `O(n)`	String cleaning
Palindrome Algorithms
Palindrome Check	`O(n)`	`O(1)`	Validation
Longest Palindrome	`O(n²)`	`O(1)`	Substring finding
Manacher's Algorithm	`O(n)`	`O(n)`	Optimal palindrome finding
Anagram & Permutation
Anagram Check	`O(n log n)` or `O(n)`	`O(1)` or `O(k)`	Anagram detection
Group Anagrams	`O(n * m log m)`	`O(nm)`	Grouping similar strings
Generate Permutations	`O(n! * n)`	`O(n! * n)`	All arrangements
Sliding Window
Longest Substring	`O(n)`	`O(min(m,n))`	Substring problems
Min Window Substring	`O(n + m)`	`O(m + n)`	Pattern matching
Character Replacement	`O(n)`	`O(1)`	String modification
Dynamic Programming
LCS	`O(nm)`	`O(nm)`	Subsequence finding
Edit Distance	`O(nm)`	`O(nm)`	String similarity
Distinct Subsequences	`O(nm)`	`O(nm)`	Counting subsequences

Common Patterns to Remember

1. Two Pointer Pattern

Perfect for palindromes and sorted array problems:

let left = 0, right = str.length - 1;
while (left < right) {
    // Process characters at left and right
    left++;
    right--;
}

2. Sliding Window Pattern

For substring problems with constraints:

let left = 0;
for (let right = 0; right < str.length; right++) {
    // Expand window
    while (/* window invalid */) {
        // Shrink window
        left++;
    }
    // Update result
}

3. Character Frequency Pattern

Using Map or object for character counting:

const freq = new Map();
for (const char of str) {
    freq.set(char, (freq.get(char) || 0) + 1);
}

4. Dynamic Programming Pattern

For comparing two strings:

const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        if (str1[i-1] === str2[j-1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        } else {
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

5. Preprocessing Pattern

Building auxiliary data structures:

// LPS array for KMP
function computeLPS(pattern) {
    const lps = new Array(pattern.length).fill(0);
    let len = 0, i = 1;

    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

Key Interview Tips

1. String Immutability

Remember that strings are immutable in JavaScript:

// Inefficient - creates new string each time
let result = "";
for (let i = 0; i < n; i++) {
    result += char; // O(n²) time complexity
}

// Efficient - use array then join
const chars = [];
for (let i = 0; i < n; i++) {
    chars.push(char);
}
const result = chars.join(''); // O(n) time complexity

2. Edge Cases to Consider

Empty string ""
Single character string "a"
All same characters "aaaa"
No repeating characters "abcd"
Special characters and spaces
Case sensitivity

3. Common String Methods

// Essential JavaScript string methods
str.charAt(i)           // Get character at index
str.charCodeAt(i)       // Get ASCII code
str.substring(i, j)     // Extract substring
str.slice(i, j)         // Extract substring (supports negative indices)
str.indexOf(substr)     // Find first occurrence
str.lastIndexOf(substr) // Find last occurrence
str.split(delimiter)    // Split into array
str.replace(old, new)   // Replace occurrences
str.toLowerCase()       // Convert to lowercase
str.toUpperCase()       // Convert to uppercase
str.trim()             // Remove whitespace

4. ASCII and Character Codes

// Useful for character manipulation
'a'.charCodeAt(0) - 'a'.charCodeAt(0) = 0  // a = 97
'z'.charCodeAt(0) - 'a'.charCodeAt(0) = 25 // z = 122
'A'.charCodeAt(0) - 'A'.charCodeAt(0) = 0  // A = 65
'Z'.charCodeAt(0) - 'A'.charCodeAt(0) = 25 // Z = 90
'0'.charCodeAt(0) - '0'.charCodeAt(0) = 0  // 0 = 48
'9'.charCodeAt(0) - '0'.charCodeAt(0) = 9  // 9 = 57

// Convert between cases
const lowerToUpper = char => String.fromCharCode(char.charCodeAt(0) - 32);
const upperToLower = char => String.fromCharCode(char.charCodeAt(0) + 32);

5. Regex Patterns for Common Operations

// Remove non-alphanumeric characters
str.replace(/[^a-zA-Z0-9]/g, '');

// Remove vowels
str.replace(/[aeiouAEIOU]/g, '');

// Split on multiple delimiters
str.split(/[,\s]+/);

// Match email pattern
/^[^\s@]+@[^\s@]+\.[^\s@]+$/.test(email);

// Match phone number
/^\d{3}-\d{3}-\d{4}$/.test(phone);

Practice Problems Categories

Easy Level

Reverse String
Valid Palindrome
First Unique Character
Valid Anagram
Implement strStr()
Length of Last Word
Roman to Integer

Medium Level

Longest Palindromic Substring
Longest Substring Without Repeating Characters
Group Anagrams
Minimum Window Substring
Longest Repeating Character Replacement
Palindromic Substrings
String Compression

Hard Level

Edit Distance
Regular Expression Matching
Wildcard Matching
Shortest Palindrome
Distinct Subsequences
Minimum Number of Taps to Open to Water a Garden
Text Justification

Advanced Topics for Further Study

Suffix Trees and Suffix Arrays
Aho-Corasick Algorithm (Multiple pattern matching)
Boyer-Moore Algorithm (Pattern matching)
String Hashing Techniques
Finite State Automata for pattern recognition
Trie Data Structure for prefix matching
Rolling Hash for substring operations
Burrows-Wheeler Transform for compression

Table of Contents​

Basic String Operations​

1. String Traversal​

2. Character Frequency Count​

3. String Comparison​

4. String Conversion Utilities​

Pattern Matching Algorithms​

1. Naive Pattern Search​

2. KMP (Knuth-Morris-Pratt) Algorithm​

3. Rabin-Karp Algorithm​

String Manipulation Techniques​

1. String Reversal​

2. Remove Characters​

3. String Compression​

Palindrome Techniques​

1. Check if String is Palindrome​

2. Longest Palindromic Substring​

3. All Palindromic Substrings​

Anagram and Permutation​

1. Check if Two Strings are Anagrams​

2. Group Anagrams​

3. Generate All Permutations​

Sliding Window Techniques​

1. Longest Substring Without Repeating Characters​

2. Minimum Window Substring​

3. Longest Repeating Character Replacement​

Two Pointer Techniques​

1. Valid Palindrome​

2. Two Sum in Sorted Array (String Version)​

3. Container With Most Water (String Analogy)​

Advanced String Algorithms​

1. Z Algorithm​

2. Manacher's Algorithm (Longest Palindromic Substring)​

3. Suffix Array​

Dynamic Programming with Strings​

1. Longest Common Subsequence​

2. Edit Distance (Levenshtein Distance)​

3. Distinct Subsequences​

Usage Examples​

Time Complexity Summary​

Common Patterns to Remember​

1. Two Pointer Pattern​

2. Sliding Window Pattern​

3. Character Frequency Pattern​

4. Dynamic Programming Pattern​

5. Preprocessing Pattern​

Key Interview Tips​

1. String Immutability​

2. Edge Cases to Consider​

3. Common String Methods​

4. ASCII and Character Codes​

5. Regex Patterns for Common Operations​

Practice Problems Categories​

Easy Level​

Medium Level​

Hard Level​

Advanced Topics for Further Study​

Table of Contents